package com.qch.edu.sort.gaojiSort;

/**
 * @Author qch
 * @Date 2021/3/6
 * 归并排序（需要递归）：稳 N*log^n,空间O(N)(方法调用结束就销毁了0)
 * 前提：两个子数组排好序，子数组的子数组也要排好
 * 如果两个数组已经有顺序，重新分配另一个数组空间和原数组等长，新数组第一个指针记为k
 * 原数组开头记为i,后半截开始位置记为k
 * 1,4,6,7,10  2,3,5,8,9
 * i           j
 * i<j ,i+1
 * a[i] 放入a[k],k+1
 * 应用：java对象排序也是归并(要求稳定)
 * BinarySort(二分排序)
 * TimSort（多路归并）分成很多分,然后两两归并（归并排序）
 */
public class MergeSort {
    public static void main(String[] args) throws Exception {
        int[] arr={1,4,7,8,5,77,3,6,9,44};
        sort(arr,0,arr.length-1);
        print(arr);
    }
    static void sort(int arr[],int left,int right) throws Exception {
       // merge(arr,0,4,arr.length-1);
        if (left<0||right<0||left>right){
            throw new Exception();
        }
        if(left==right)return;
        //分成两半
        int mid=left+(right-left)/2;
        //左边排序
        sort(arr,left,mid);
        //右边排序
        sort(arr,mid+1,right);
        merge(arr,left,mid+1,right);
    }
    static void merge(int[] arr,int leftPtr,int rightPtr,int rightBound)
    {
        int mid=rightPtr-1;
        int[] temp=new int[rightBound-leftPtr+1];
        int i=leftPtr;
        int j=rightPtr;
        int k=0;
        while (i<=mid&&j<=rightBound) {
            //小于等于稳定，小于不稳定
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i<=mid)
        {
            temp[k++]=arr[i++];
        }
        while (j<=rightBound)
        {
            temp[k++]=arr[j++];
        }
        for (int m = 0; m < temp.length; m++) {
            arr[leftPtr+m]=temp[m];
        }
        //print(temp);

    }
    static void mergeFirst(int arr[]){
        int mid=arr.length/2;
        int[] temp=new int[arr.length];
        int i=0;
        int j=mid+1;
        int k=0;
        while (i<=mid&&j<arr.length){
            //小于等于稳定，小于不稳定
            if(arr[i]<=arr[j])
            {
                temp[k]=arr[i];
                i++;
                k++;
            }else {
                temp[k]=arr[j];
                j++;
                k++;
            }

        }
        while (i<=mid)
        {
            temp[k++]=arr[i++];
        }
        while (j<arr.length)
        {
            temp[k++]=arr[j++];
        }

        print(temp);

    }
    static void swap(int[] arr,int i,int j)
    {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    static void print(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+",");
        }
    }
}
